#include <stdio.h>
#include <stdlib.h>

//二叉排序树（BST）
/*
定义：左子树结点值 < 根结点值 < 右子树结点值
中序遍历该树得到递增的有序序列


*/

typedef struct BSTNode
{
    int key;
    struct BSTNode *lchild, *rchild;
} BSTNode, *BSTree;

//查询
/*
查找长度：一次查询过程中，对比关键字的次数
*/
BSTNode *BST_Search(BSTree T, int key)
{
    while (T != NULL && key != T->key)
    {
        if (key < T->key)
        {
            T = T->lchild;
        }
        else
        {
            T = T->rchild;
        }
    }
    return T;
}

//插入
int BST_Insert(BSTree &T, int k)
{
    if (T == NULL)
    {
        T = (BSTNode *)malloc(sizeof(BSTNode));
        T->key = k;
        T->lchild = T->rchild = NULL;
        return 1;
    }
    else if (k == T->key) //如果已存在，则不插入
    {
        return 0;
    }
    else if (k < T->key) //插入T的左子树
    {
        return BST_Insert(T->lchild, k);
    }
    else //插入T的右子树
    {
        return BST_Insert(T->rchild, k);
    }
}

//构造
void Creat_BST(BSTree &T, int str[], int n)
{
    T = NULL;
    int i = 0;
    while (i < n)
    {
        BST_Insert(T, str[i]);
        i++;
    }
}


//删除
/*
(1)如果是叶子结点，则直接删除
(2)如果当前结点只有左子树或者右子树，让子树代替当前结点
(3)
1、令该结点的直接后继代替该结点，并删除这个直接后继
中序遍历中，可以得到一个递增的有序序列，那个直接后继就是，该结点右子树中序遍历的第一个数
也是最左下结点（该结点一定没有左子树）
2、或者用直接前驱，该结点左子树的最右下结点
*/




int main()
{
    printf("\n\n========================================================================\n\n");

    printf("\n\n========================================================================\n\n");
    return 0;
}